note: the printed out copies fail to make
"delay, dx, dy" static.
Also, be sure to check out the sample output
(link
below):
----------------------------------------------------------------------------
public class Robot implements Runnable {
private Motor motor; //
robot's motor
private int size; // width
and height of rock crater
private Sensor gnatx, gnaty; // sensors for gnat's position
private DiagnosticPanel panel; // debugging panel for drawing plans and known
rocks
// constructor: fill in fields above with supplied
values
public Robot(int
size, Motor m, Sensor sx, Sensor sy, DiagnosticPanel p)
{
this.size = size;
motor = m; gnatx = sx; gnaty = sy; panel = p;
}
// run (control) the robot
public void run() {
final int delay = 5; //
how many ticks motor needs to move
int
d; // index of a
direction
final int[] dx = { 0, 1, -1, 0 }; // x offset of a direction
final int[] dy = { 1, 0, 0, -1 }; // y offset of a direction
int[][] map =
// map of known rocks and distances to
gnat
new
int[1+size+1][1+size+1]; // with border
of rocks (hence 1+ and +1)
final int INFINITY = 2*size*size; // mark unvisited/unreachable map locations
final int ROCK = INFINITY + 1; // mark known rocks in map
int
x = motor.x.value(), y = motor.y.value(); // robot location
// place rocks on border, but don't register
them
for (int i=0; i<1+size+1;
i++)
map[i][0] =
map[i][1+size] = map[0][i] = map[1+size][i] = ROCK;
while (true)
{
int gx = gnatx.value(), gy
= gnaty.value(); // gnat location
// reset non-ROCKs in map to INFINITY for
floodflill
for (int i=1;
i<=size; i++)
for (int j=1; j<=size; j++)
if (map[i][j] != ROCK) map[i][j] =
INFINITY;
//
floodfill
//
frontier[0..1][front..back-1] is the to-do list of places
whose
// neighbors might be
unvisited; frontier[0] is y-values, frontier[1]
is
// x-values. frontier is
seeded with (x,y), set at distance 0 in map
int[][] frontier = new
int[2][size*size];
int front = 0, back =
1;
frontier[0][front] = y;
frontier[1][front] = x;
map[y][x] = 0;
// keep
growing out frontier until frontier is empty or reach the
gnat
while (front<back && map[gy][gx] ==
INFINITY) {
// remove next place (px,py) from to-do
list
int py = frontier[0][front], px =
frontier[1][front];
front++;
// add unvisited neighbors (nx,ny) to to-do list &
set distances
for (d=0; d<dx.length; d++)
{
int ny = py + dy[d], nx = px +
dx[d];
if (map[ny][nx] == INFINITY)
{
map[ny][nx] = 1 +
map[py][px];
frontier[0][back] =
ny;
frontier[1][back] = nx;
back++;
}
}
}
int
steps = map[gy][gx]; // number of steps to
reach gnat
if (steps == INFINITY) throw new
RuntimeException("Gnat unreachable!");
int[][] plan = frontier; // reuse frontier (no longer used) for plan
// traceback:
move (gx,gy) backwards to 1 unit away from robot --to
where
// robot moves in next
step-- and place steps (gx,gy) into the plan
while (map[gy][gx]>1)
{
plan[0][map[gy][gx]] = gy; plan[1][map[gy][gx]] = gx;
// search for direction d where neighbor is 1 unit
closer
for (d=0;
1+map[gy+dy[d]][gx+dx[d]] != map[gy][gx];
d++)
;
gy
+= dy[d]; gx += dx[d]; // move to neighbor found
above
}
// add (gx,gy) and robot's positions to plan and register
it
plan[0][map[gy][gx]] = gy; plan[1][map[gy][gx]] =
gx;
plan[0][0] = y;
plan[1][0] =
x;
panel.registerPlan(steps,plan[1],plan[0]);
// move to (gx,gy) if not already
there
if (gx != x || gy != y) {
// search for direction d from which to reach (gx,gy)
from (x,y)
for (d=0; y+dy[d] != gy ||
x+dx[d] != gx;
d++)
;
motor.move(d); // try to move in direction found
above
}
// give
motor (or gnat) time to move (away)
for (int t =
delay + motor.clock(); t > motor.clock();
)
;
x = motor.x.value();
y = motor.y.value(); // read x,y from motor
sensors
// register a
rock if robot has not moved and update map
if (x != gx || y != gy)
{
panel.registerRock(gx,gy);
map[gy][gx] =
ROCK;
}
}
}
}